Round Overview
Discuss this match
There are many pairs of colors we can use for the checkered pattern. There are at most 26 colors. So we have 26 options for the first color and 25 options for the second color (the two colors must be distinct). 26*25 = 650. We can try all possible color combinations and see what cost that gives. Then pick the minimum cost among all the costs we find. To find the cost, first generate the board using the two picked colors then compare this new board with the input board and count the number of cells that need to change.
We can tell which color the cells in the wanted board should have by using the parity of the cell’s coordinates. A cell with coordinates `(i,j)` will be of one color if `i + j` is even and the other color if `i + j` is odd.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int minimumChanges(vector < string > floor) {
int N = floor.size();
int res = N * N;
// for each pair of colors (A,B):
for (char A = 'a'; A <= 'z'; A++) {
for (char B = 'a'; B <= 'z'; B++) {
if (A != B) {
// Calculate the cost:
int cost = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// what color should cell (i,j) be?
char z = (((i + j) % 2) ? A : B);
// If they differ, increment cost
if (floor[i][j] != z) {
cost++;
}
}
}
// keep track of the minimum
res = std::min(res, cost);
}
}
}
return res;
}
We have an initial string and an target string. What helps in this problem is to think backwards. Given the target string, can we guess what was the last move? First understand the two kinds of moves:
Add an ‘A’ to the end of the string. This means that after this move , the string will end with ‘A’
Reverse the string and add a ‘B’ to the end. This time the string will end with ‘B’
We can tell the type of the last move by just looking at the last character in the string. More importantly, we have enough information to undo the last move:
If the last character of the target is ‘A’, the last move consisted of appending ‘A’ to the string, we can undo this by just removing this last letter ‘A’.
If the last character is ‘B’, then the move consisted of first reversing and then adding ‘B’. We can undo this move by first removing the last ‘B’ and then reversing the remaining string.
For any given target string, we can undo the last move. We can even repeat this procedure until the target and the initial string are equal or until it becomes clear that this will never happen. Each move reduces the number of characters in the target by one, so we can repeat this until the target and initial strings have an equal number of characters. If in this state, the strings are distinct, we can be certain the case is impossible, else it is possible.
1
2
3
4
5
6
7
8
9
10
11
12
13
string canObtain(string initial, string target) {
// While the target is longer:
while (target.size() > initial.size()) {
if (target.back() == 'A') { // Undo an 'A' move:
target.pop_back(); // simply remove the last character
} else { // Undo a B move:
target.pop_back(); // remove
reverse(target.begin(), target.end()); // and reverse
}
}
return (initial == target) ? "Possible" : "Impossible";
}
We need to be able to answer the following question: "Given a set of competitors and a player that belongs to the set and knowledge of which player will win each possible match up, count the number of orderings in which the given player will win the tournament.
What we can do is represent this as `f(i, S)`, where `i` is the player in question and `S` the set of players available in this tournament. We want to play with recursion so we need a way to divide the problem into smaller versions of this problem. Consider this: An elimination tournament of 16 players can be seen as two tournaments of 8 distinct players each plus a last match between the winners of the two smaller tournaments. When given `|S|` players, we want to divide them in two disjoint halves: `S_1` and `S_2`, the only thing we’ll know about the order is that players in `S_2` will be ordered after `S_1`. So `S_1` and `S_2` will each have one winner. We are interested in scenarios in which player `i` wins `S_1` or `S_2` (Depending of which one `i` was included in). There are two cases, in one of the cases `i` is in `S_1`; There are `f(i, S_1)` ways in which `i` will win `S_1`. For each `j` in `S_2`, it is possible that `j` wins the mini-tournament of `S_2` a total of `f(j, S_2)` times. If according to our match up rules, `i` wins after matched against `j`, then we need to add `f(i, S_1) times f(j, S_2)` to the final result, because those are the number of ways in which `i` versus `j` is the final match in the tournament AND thus ways in which `i` wins. Consider the cases in which `i` is in `S_2`. Due to symmetry, this will look exactly the same, so in fact we should be adding `2 times f(i, S_1) times f(j, S_2)` to the result.
All last paragraph describes the solution to the problem. But we need to flesh things out. First of all, the function `f(i, S)` takes a subset of the initial list of players. There are `O(2^n)` possible subsets. Although in practice, the subset will always have a power of two number of elements. This difference is not extremely important and only reduces the number of sets to 6 times smaller. So we will still consider it `O(2^n)` for simplicity. There are `n` possible values for `i`. So there are `O(n 2^n)` possible inputs for `f(i,S)`, we can use memoization here so that each of the configurations is processed exactly once. Bit masks are popular when dealing with subsets and memoization. So now our function looks like: f(i, mask).
We need a base case. Each time you split the set in half, the tournaments will get smaller and smaller. Eventually we will have instances of f(i, mask) in which the mask represents a set of exactly one element (i). This is an easy base case because this mini tournament will always be won by i, and there is exactly one possible order for it. So the result is 1 in this case.
Now the more interesting part is to split the subset `S` (or the mask) into two sets `S_1` and `S_2` such that `S_1` contains `i`. We need all the possible values of `S_1`. We can start by precalculating, for each possible `S`, the possible values of `S_1`. Note that `S_1` must have exactly half the elements of `S`. Also note that if `S_1` is known, we can find `S_2` by taking its complement (The elements not in `S_1` will be in `S_2`). This precalculation requires us to visit all sets `S` and all its subsets. In the Bit masks article above there are instructions for a way to do this in `O(3^n)` time. Now note that for each `f(i, S)` we will also iterate all subsets of `S`. This means that the total complexity will be `O(n^2 3^n)`. The rest is to implement all these ideas in code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
int n;
long long dp[16][1 << 16];
vector < string > wins;
vector < vector < int >> mask_splits;
long long f(int i, int mask) {
long long & res = dp[i][mask];
if (res == -1) {
int t = __builtin_popcount(mask);
if (t == 1) {
//base case, the player is alone
res = 1;
} else {
res = 0;
// for each possible S1
for (int mask1: mask_splits[mask]) {
// that contains i:
if (mask1 & (1 << i)) {
int mask2 = (mask & ~mask1); //complement of S1 intersection S
for (int j = 0; j < n; j++) {
// for each j that might win mask2 and loses against i:
if ((wins[i][j] == 'Y') && (mask2 & (1 << j))) {
res += 2 * f(i, mask1) * f(j, mask2);
}
}
}
}
}
}
return res;
}
vector < long long > waysToWin(vector < string > wins) {
n = wins.size();
this - > wins = wins;
// precalculate the list of proper subsets of half the set size for each set:
mask_splits.resize(1 << n);
for (int mask = 1; mask < (1 << n); mask++) { // for each set
// for each subset:
for (int sub = (mask - 1) & mask; sub > 0; sub = (sub - 1) & mask) {
// proper size:
if (__builtin_popcount(sub) * 2 == __builtin_popcount(mask)) {
// save in list
mask_splits[mask].push_back(sub);
}
}
}
// The solution:
memset(dp, -1, sizeof(dp));
vector < long long > res(n);
for (int i = 0; i < n; i++) {
res[i] = f(i, (1 << n) - 1);
}
return res;
}
Like in the division 2 version, we can try and focus on the last move used. This time things vary, however:
If the move consisted of adding ‘A’, then the string will have an ‘A’ in its last position.
If the move consisted of adding ‘B’ and then reversing, the ‘B’ will now be in the first position of the string.
If we tried the idea from division 2, if the string ends with ‘A’ or starts with ‘B’, then we can undo the last move… However, there is a complication when the string both begins with ‘B’ and ends with ‘A’. Both kinds of moves would be valid candidates for the last move. So now we have to choose between two modified target strings, one of them might be the one that can become initial after undoing more moves, but we don’t know which until we test them.
We can approach this by thinking of a recursive function f(target). If f(target) is true, then it is possible to reach this target starting from string initial. Else it is not possible.
Base case: If target and initial have the same length, then they must be equal, then it is possible, otherwise, it is impossible.
If target finished with an ‘A’, then we can assume the last move was appending ‘A’, we can undo it by removing the ‘A’. We still need to find out if the new string target’ can be reached from initial. If f(target’) is true, then assuming this was the last move was the right idea and we can return true for f(target)
If target begins with ‘B’, we can remove the starting ‘B’ and reverse the string. The new target’’ is a possible candidate. If f(target’’) is true, then we can return true for f(target).
If after trying those candidate strings, we couldn’t find a possible case or if neither of those cases was valid (A string that begins with A and ends with B). Then the result is false.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
string canObtain(string initial, string target) {
if (initial == target) {
return "Possible";
}
if (target.size() > 0) {
if ((target.back() == 'A') && (canObtain(initial, cut(target)) == "Possible")) {
return "Possible";
}
if ((target[0] == 'B') && (canObtain(initial, cut(reverse(target))) == "Possible")) {
return "Possible";
}
}
return "Impossible";
}
1
2
3
4
5
6
7
8
9
10
11
class ABBADiv1:
def canObtain(self, initial, target):
def can(s):
if initial == s:
return True
if len(s) > 0:
return ((s[0] == 'B') and can(s[: 0: -1])) or((s[-1] == 'A') and can(s[: -1]))
return False
return "Possible"
if can(target)
else "Impossible"
The result is nicely clean code, but before we implement it we need to make sure it’d run in time. This is the reason most coders preferred to implement this using dynamic programming or to implement it as a Breadth-First Search.
The time execution concern in recursive solutions is that it’s not always easy to tell how many times will the recursive function get called. Every time we call f(), the number of characters in target decreases by 1. So the recursion depth will be `O(n)`. What about the number of branches? We are interested in cases where the first character is B and the last character is A, these are the cases that require the function instance to branch into two new instances:
BX…YA
If we pick the move A, then the new string will be BX…Y, if Y is A, then the execution can branch again. Else it cannot and we will be forced to use a B move.
More interestingly, if we choose B as the last move, the new string is: AY…X. This string cannot branch again even if X is A. In fact, this string will never branch anymore. No matter what we do, all the next moves we undo have to be those of the kind in which we append an ‘A’ to the end of the string. We will not be able to undo any ‘B’ moves again.
In order to maximize the number of branches we will need to go for a string like “BAAAAAAAAA…A”. For example, for `n = 5`: BAAAA:
BAAAA
|
- AAAA - AAA - AA - A
|
- BAAA
|
- AAA - AA - A
|
- BAA
|
- AA - A
|
- BA
|
- A
|
- B
So even in this worst case, we will have exactly `n - 1` situations in which there is a branch. Even if we factored `n` recursion depth for each of them we will only call `f()` a total of `O(n^2)` times. This means that the above python and c++ solutions doing straight-forward recursion will be very fast. Add a linear factor for the required string copying and reversing . This algorithm is `O(n^3)` even when implemented without memoization/dynamic programming.
Let’s consider each case (removing a certain amount of coins of a single type) separately. There can be up to 2000 of those cases, so we need to be able to solve each in 0.001 seconds. That is one significant time constraint.
We initially have the list ways that tells us how many ways to have each amount of money there are by using different coins. We want to find the number of ways to make `D-1` money after we remove one of the coins.
To understand better what we want, first consider the opposite problem: We add `r` coins of value `v`. How does it change the number of ways? It 's better to first solve a simplified version of this: Add a single coin of value 1.
We can use a dynamic programming-esque concept and use the original ways array as information to build a new one after adding the one coin. Start from `i = 0` until `i = D - 1`:
For `i = 0`, `w[0] = 1` means there is exactly one way to use the coins to represent 0. Adding a coin of value 1 does not change this. So `w’[0] = 1`
For other `i`, consider that there were initially `w[i]` ways to have value `i` using the previously existing coins. It is also possible to take each of the `w[i-1]` ways to have `(i-1)` and add the coin to that configuration. In short: `w’[i] = w[i-1] + w[i]`.
With this, imagine we start with a row of ways:
ways = 1 5 6 7
We can calculate a new row after adding a new coin, just use: `w’[i] = w[i-1] + w[i]`
ways’ = 1 6 11 13 7
So how about when we add more than one coin? We just repeat the process:
ways’’ = 1 7 17 24 20 7
ways’’’= 1 8 24 41 44 27 7
…
We can also generalize to `v != 1`, just know that `w’[i] = w[i-v] + w[i]`
What we want is to be able to do the reverse operation, first of all, if `r = 1` and `v = 1`, we want to find the row that came before the one we are given right now. It is not really difficult, note that `w[i]= w’[i] - w[i-1]`. For example, if ways’ = 1 5 6 7
ways’ = 1 5 6 7
…
**ways ** = 1 4 2 5
From here it would be easy to solve the problem if not for the 0.001 seconds limit. We would just do this `O(D)` procedure `O®` times. Until we find the original row before adding all those `r` coins. Unfortunately, `r` can be quite large, and in fact we should aim towards an `O(D)` solution or something close. What can we do know?
If we take `w’[i] = w[i-1] + w[i]` it looks very similar to Pascal’s triangle which has a reduction to Binomial coefficients. It would seem that the more general version and in reverse should also have a similar reduction. But how can we find it?
A nice method is to take the operation in which we turn a row into the next one and formalize it in a different way. That way we can know more about how to do the inverse of the operation.
**ways ** = 1 5 6 7
ways’ = 1 6 11 13 7
ways’’ = 1 7 17 24 20 7
ways’’’= 1 8 24 41 44 27 7
One way is to see each row as the coefficients of a polynomial. So we initially have `1 + 5x^2 + 6x^3 + 7x^4`, we do an operation and we turn it into `1 + 6x^2 + 11x^3 + 13x^4 + 7x^5`. This might appear a fruitless endeavor, but how about we try to find the operation behind this transformation?
So the new coefficients are `w’[i] = w[i] + w[i-1]`. This means that If the first polynomial is `sum (w[i] x^i)` then the new polynomial will be:
`sum( (w[i] + w[i-1]) x^i )`
`= sum(w[i]x^i + w[i-1]x^i)`
`= sum(w[i]x^i) + sum(w[i-1]x^i)`
`= sum(w[i]x^i) + sum(w[i-1]x^(i-1) * x)`
`= sum(w[i]x^i) + x * sum(w[i-1]x^(i-1) )`
`= sum(w[i]x^i) + x * sum(w[i]x^i )`
The new polynomial is equal to the addition of the old polynomial plus the old polynomial multiplied by `x`. That’s quite nice isn’t it? It’s as if `B = A + Ax = A(1 + x)`. The new polynomial is equal to multiplying the old polynomial by `(x + 1)`. Note that to generalize for `v != 1`, we would have to multiply by `(x^v + 1)`.
If to make the next row we multiply by `(x + 1)` then to get the previous row we multiply by `1 / (x+1)`. So now we just need to find the coefficients of the resulting polynomial after we multiply `sum(w[i]x^i)` by `(1 / (x + 1))^r`.
That last find doesn’t seem all that helpful, but we should try more. Did you know `(1 / (x+1)) = 1 - x + x^2 - x^3 + x^4 - … `? (Read: Taylor series). For `v != 1`, we would use: `(1 / (x^v+1)) = 1 - x^v + x^(2v) - x^(3v) + x^(4v) - … ` . This might be more helpful because it turns the problem back to a multiplication by a polynomial instead of a division.
We need to find the coefficients of: `(1 - x + x^2 - x^3 + x^4 - …) ^ r`. We don’t need all the coefficients. Remember, we will multiply the original polynomial: `sum(w[i] x^i)` by `(1 - x + x^2 - x^3 + x^4 - …) ^ r`, and we are looking for the coefficient of `x^D` in this polynomial. Hence why we’ll need only those coefficient with `i <= D`. So we want all the first `D+1` coefficients of: `(1 - x + x^2 - x^3 + x^4 - …) ^ r`. By using the same argument, we can use a finite polynomial instead: `(1 - x + x^2 - x^3 + x^4 - … ± x^D) ^ r` . A complication is that the signs alternate. Let’s first try a simple case: `(1 - x + x2)3`:
`(1 - x + x2)3`
` = (x^4 - 2x^3 + 3x^2 - 2x + 1) (1 - x + x^2)`
` = x^6 - 3x^5 + 6x^4 - 7x^3 + 6x^2 - 3x + 1`
The signs in the result alternate as well and if we raise: `(1 + x + x2) 3 x^6 + 3x^5 + 6x^4 + 7x^3 + 6x^2 - 3x + 1`. Those are the same coefficients. If this rule applies to any `D` and `r`, then we will have a chance to solve this problem. You can prove by induction that this is true. It is true for `r = 1` (The signs already alternate), and we just need to show that if it is true for `r` it will be true for `r+1`.
So now we just need to find the (D+1)-th coefficient of `(1 + x + x^2 + … + xD)r`. Consider multiplying `A` by `(1 + x + x^2 + … + x^D)`, this would mean: `A + Ax + Ax^2 + …`. Let’s name the i-th coefficient of A `a_i` and the i-th coefficient of the new product `b_i`. Let’s try to find `b_i`: `a_i x^i` will be multiplied by 1, `a_(i-1)x^(i-1)` will be multiplied by `x`, `a_(i-2)x^(i-2)` will be multiplied by `x^2` and so and so. We will have: `b_i = a_0 + a_1 + … a_i`. In other words, this is like running a running sum on all the coefficients of `A`. So we need to do multiple running sums on an initial sequence of 1 1 1 1 1 … 1. This is a problem that can be reduced to Binomial Coefficients as we’ve previously seen in the editorial for SRM 467 problem: SuperSum. So the i-th coefficient of after raising to the r-th exponent will be: `( (i+r-1), (i) )`. Note that we need to add a sign, if `i` is even the sign is + else -: `(-1)^i( (i+r-1), (i) )`.
We multiply the original polynomial: `sum(w[i]x^i)` by the new one: `sum( (-1)^i( (i+r-1), (i) ) x^i)` and want the D-th coefficient. We will find the result is: `sum( (-1)^i( (i+r-1), (i) ) w[D - i] )`.
What about `v != 1`? First of all the running sum works different, using skips of length `v`. So for coefficient `D` , we will need `D - v, D- 2*v, D-3*v, ` instead of just `D - 1, D- 2, D-3`. Otherwise it will be a very similar formula: `sum( (-1)^i( (i+r-1), (i) ) w[D - i*v] )`. Note that `D - i*v >= 0` otherwise the value of `w[D-i*V]` is 0, thus we need to consider only `i <= D/v` in this sum.
For implementing we need to do calculate the Binomial Coefficients quickly. We can do it in `O(1)` time if we precalculate the relevant factorials (modulo 1000000007) and also the modular multiplicative inverse of the factorials (so we can do the division part of the binomial coefficient formula. See comments in code for more info
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
const int MOD = 1000000007;
// Calculate the power (x ^ y) mod M
long mod_pow(long x, long y) {
long r = 1;
while (y > 0) {
if (y % 2 == 1) {
r = (r * x) % MOD;
}
x = (x * x) % MOD;
y /= 2;
}
return r;
}
// modular multiplicative inverse using Fermat's Little Theorem:
long mod_inverse(long x) {
return mod_pow(x, MOD - 2);
}
const int MAX = 1005000;
vector < long > f, fi;
// The binomial coefficient modulo M
long C(int n, int k) {
assert(n < MAX);
assert(k < MAX);
if (k > n) {
return 0;
}
return (f[n] * ((fi[k] * fi[n - k]) % MOD)) % MOD;
}
int sub_case(const vector < int > & ways, int v, int r) {
long res = 0;
int D = ways.size() - 1;
// summation of:
int i = 0;
while (D - i * v >= 0) {
long x = ways[D - i * v];
// if D-i*v is too small there are 0 ways to do it
x = (x * C(r + i - 1, i)) % MOD;
// add when it is even, subtract when it is odd:
if (i % 2 == 0) {
res = res + x;
} else {
res = res + MOD - x;
}
i++;
}
return (int)(res % MOD);
}
vector < int > countWays(vector < int > ways, vector < int > valueRemoved, vector < int > numRemoved) {
f.resize(MAX);
fi.resize(MAX);
// precalculate all factorials i! mod M:
f[0] = 1;
for (int i = 1; i < MAX; i++) {
f[i] = (i * f[i - 1]) % MOD;
}
// precalculate all multiplicative inverse of factorials (i!)^-1 mod M:
fi[MAX - 1] = mod_inverse(f[MAX - 1]); // ( (MAX-1)! ) ^ -1
for (int i = MAX - 2; i >= 0; i--) {
fi[i] = ((i + 1) * fi[i + 1]) % MOD; // 1/(x!) = (x + 1) * (1 / (x+1)!)
}
// for each case:
int m = valueRemoved.size();
vector < int > res(m);
for (int i = 0; i < m; i++) {
res[i] = sub_case(ways, valueRemoved[i], numRemoved[i]);
}
return res;
}